home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsI / Original / GenericPolygonScan.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-16  |  17.9 KB  |  640 lines  |  [TEXT/MPS ]
  1. /*
  2. Generic Convex Polygon Scan Conversion and Clipping
  3. by Paul Heckbert
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. /* poly.h: definitions for polygon package */
  8.  
  9. #ifndef POLY_HDR
  10. #define POLY_HDR
  11.  
  12. #define POLY_NMAX 8    /* max #sides to a polygon; change if needed */
  13.  
  14. typedef struct {        /* A POLYGON VERTEX */
  15.     double sx, sy, sz, sw;     /* screen space position  */
  16.                             /* (sometimes homo.) */
  17.     double x, y, z;        /* world space position */
  18.     double u, v, q;        /* texture position */
  19.                         /* (sometimes homogeneous) */
  20.     double r, g, b;        /* (red,green,blue) color */
  21.     double nx, ny, nz;        /* world space normal vector */
  22. } Poly_vert;
  23. /* update poly.c if you change this structure */
  24.  
  25. typedef struct {        /* A POLYGON */
  26.     int n;            /* number of sides */
  27.     int mask;            /* interpolation mask for vertex elems */
  28.     Poly_vert vert[POLY_NMAX];    /* vertices */
  29. } Poly;
  30. /*
  31.  * mask is an interpolation mask whose kth bit indicates whether the kth
  32.  * double in a Poly_vert is relevant.
  33.  * For example, if the valid attributes are sx, sy, and sz, then set
  34.  *    mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz);
  35.  */
  36.  
  37. typedef struct {        /* A BOX (TYPICALLY IN SCREEN SPACE) */
  38.     double x0, x1;        /* left and right */
  39.     double y0, y1;        /* top and bottom */
  40.     double z0, z1;        /* near and far */
  41. } Poly_box;
  42.  
  43.  
  44. typedef struct {        /* WINDOW: A DISCRETE 2-D RECTANGLE */
  45.     int x0, y0;            /* xmin and ymin */
  46.     int x1, y1;            /* xmax and ymax (inclusive) */
  47. } Window;
  48.  
  49. #define POLY_MASK(elem) (1 << (&poly_dummy->elem - \
  50.                              (double *)poly_dummy))
  51.  
  52. #define POLY_CLIP_OUT 0        /* polygon entirely outside box */
  53. #define POLY_CLIP_PARTIAL 1    /* polygon partially inside */
  54. #define POLY_CLIP_IN 2        /* polygon entirely inside box */
  55.  
  56. extern Poly_vert *poly_dummy;    /* used superficially by */
  57.                             /* POLY_MASK macro */
  58.  
  59. void    poly_print(/* str, p */);
  60. void    poly_vert_label(/* str, mask */);
  61. void    poly_vert_print(/* str, v, mask */);
  62. int        poly_clip_to_box(/* p1, box */);
  63. void    poly_clip_to_halfspace(/* p, q, index, sign, k, name */);
  64. void    poly_scan(/* p, win, pixelproc */);
  65.  
  66. #endif
  67.  
  68.  
  69. /*
  70.  * poly.c: simple utilities for polygon data structures
  71.  */
  72.  
  73. #include "poly.h"
  74.  
  75. Poly_vert *poly_dummy;    /* used superficially by POLY_MASK macro */
  76.  
  77. /*
  78.  * poly_print: print Poly p to stdout, prefixed by the label str */
  79.  
  80. void poly_print(str, p)
  81. char *str;
  82. Poly *p;
  83. {
  84.     int i;
  85.  
  86.     printf("%s: %d sides\n", str, p->n);
  87.     poly_vert_label("        ", p->mask);
  88.     for (i=0; i<p->n; i++) {
  89.         printf("   v[%d] ", i);
  90.         poly_vert_print("", &p->vert[i], p->mask);
  91.     }
  92. }
  93.  
  94.  
  95. void poly_vert_label(str, mask)
  96. char *str;
  97. int mask;
  98. {
  99.     printf("%s", str);
  100.     if (mask&POLY_MASK(sx))   printf("   sx  ");
  101.     if (mask&POLY_MASK(sy))   printf("   sy  ");
  102.     if (mask&POLY_MASK(sz))   printf("   sz  ");
  103.     if (mask&POLY_MASK(sw))   printf("   sw  ");
  104.     if (mask&POLY_MASK(x))    printf("   x   ");
  105.     if (mask&POLY_MASK(y))    printf("   y   ");
  106.     if (mask&POLY_MASK(z))    printf("   z   ");
  107.     if (mask&POLY_MASK(u))    printf("   u   ");
  108.     if (mask&POLY_MASK(v))    printf("   v   ");
  109.     if (mask&POLY_MASK(q))    printf("   q   ");
  110.     if (mask&POLY_MASK(r))    printf("   r   ");
  111.     if (mask&POLY_MASK(g))    printf("   g   ");
  112.     if (mask&POLY_MASK(b))    printf("   b   ");
  113.     if (mask&POLY_MASK(nx))   printf("   nx  ");
  114.     if (mask&POLY_MASK(ny))   printf("   ny  ");
  115.     if (mask&POLY_MASK(nz))   printf("   nz  ");
  116.     printf("\n");
  117. }
  118.  
  119. void poly_vert_print(str, v, mask)
  120. char *str;
  121. Poly_vert *v;
  122. int mask;
  123. {
  124.     printf("%s", str);
  125.     if (mask&POLY_MASK(sx)) printf(" %6.1f", v->sx);
  126.     if (mask&POLY_MASK(sy)) printf(" %6.1f", v->sy);
  127.     if (mask&POLY_MASK(sz)) printf(" %6.2f", v->sz);
  128.     if (mask&POLY_MASK(sw)) printf(" %6.2f", v->sw);
  129.     if (mask&POLY_MASK(x))  printf(" %6.2f", v->x);
  130.     if (mask&POLY_MASK(y))  printf(" %6.2f", v->y);
  131.     if (mask&POLY_MASK(z))  printf(" %6.2f", v->z);
  132.     if (mask&POLY_MASK(u))  printf(" %6.2f", v->u);
  133.     if (mask&POLY_MASK(v))  printf(" %6.2f", v->v);
  134.     if (mask&POLY_MASK(q))  printf(" %6.2f", v->q);
  135.     if (mask&POLY_MASK(r))  printf(" %6.4f", v->r);
  136.     if (mask&POLY_MASK(g))  printf(" %6.4f", v->g);
  137.     if (mask&POLY_MASK(b))  printf(" %6.4f", v->b);
  138.     if (mask&POLY_MASK(nx)) printf(" %6.3f", v->nx);
  139.     if (mask&POLY_MASK(ny)) printf(" %6.3f", v->ny);
  140.     if (mask&POLY_MASK(nz)) printf(" %6.3f", v->nz);
  141.     printf("\n");
  142. }
  143.  
  144.  
  145. /*
  146.  * poly_scan.c: point-sampled scan conversion of convex polygons
  147.  *
  148.  * Paul Heckbert    1985, Dec 1989
  149.  */
  150.  
  151. #include <stdio.h>
  152. #include <math.h>
  153. #include "poly.h"
  154.  
  155. /*
  156.  * poly_scan: Scan convert a polygon, calling pixelproc at 
  157.  * each pixel with an interpolated Poly_vert structure.
  158.  *   Polygon can be clockwise or ccw.
  159.  * Polygon is clipped in 2-D to win, the screen space window.
  160.  *
  161.  * Scan conversion is done on the basis of Poly_vert fields sx and sy.
  162.  * These two must always be interpolated, and only they have 
  163.  * special meaning to this code; any other fields are 
  164.  * blindly interpolated regardless of their semantics.
  165.  *
  166.  * The pixelproc subroutine takes the arguments:
  167.  *
  168.  *    pixelproc(x, y, point)
  169.  *    int x, y;
  170.  *    Poly_vert *point;
  171.  *
  172.  * All the fields of point indicated by p->mask will be 
  173.  * valid inside pixelproc except sx and sy.
  174.  * If they were computed, they would have values
  175.  * sx=x+.5 and sy=y+.5, since sampling is done at pixel centers.
  176.  */
  177.  
  178. void poly_scan(p, win, pixelproc)
  179. register Poly *p;        /* polygon */
  180. Window *win;            /* 2-D screen space clipping window */
  181. void (*pixelproc)();        /* procedure called at each pixel */
  182. {
  183.     register int i, li, ri, y, ly, ry, top, rem, mask;
  184.     double ymin;
  185.     Poly_vert l, r, dl, dr;
  186.  
  187.     if (p->n>POLY_NMAX) {
  188.         fprintf(stderr, "poly_scan: too many vertices: %d\n", p->n);
  189.         return;
  190.     }
  191.  
  192.  
  193.     ymin = HUGE;
  194.     for (i=0; i<p->n; i++)    /* find top vertex (y points down) */
  195.         if (p->vert[i].sy < ymin) {
  196.             ymin = p->vert[i].sy;
  197.             top = i;
  198.         }
  199.  
  200.     li = ri = top;            /* left and right vertex indices */
  201.     rem = p->n;                /* number of vertices remaining */
  202.     y = ceil(ymin-.5);            /* current scan line */
  203.     ly = ry = y-1;            /* lower end of left & right edges */
  204.     mask = p->mask & ~POLY_MASK(sy); /* stop interpolating screen y */
  205.  
  206.     while (rem>0) { /* scan in y, activating new edges on left & */                  /* right as scan line passes over new vertices */
  207.  
  208.         while (ly<=y && rem>0) {    /* advance left edge? */
  209.             rem--;
  210.             i = li-1;            /* step ccw down left side */
  211.             if (i<0) i = p->n-1;
  212.             incrementalize_y(&p->vert[li], &p->vert[i], &l,
  213.                          &dl, y, mask);
  214.             ly = floor(p->vert[i].sy+.5);
  215.             li = i;
  216.         }
  217.         while (ry<=y && rem>0) {    /* advance right edge? */
  218.             rem--;
  219.             i = ri+1;            /* step cw down right edge */
  220.             if (i>=p->n) i = 0;
  221.             incrementalize_y(&p->vert[ri], &p->vert[i], &r,
  222.                          &dr, y, mask);
  223.             ry = floor(p->vert[i].sy+.5);
  224.             ri = i;
  225.         }
  226.  
  227.         while (y<ly && y<ry) 
  228.                     /* do scanlines till end of l or r edge */
  229.             if (y>=win->y0 && y<=win->y1)
  230.               if (l.sx<=r.sx) scanline(y, &l, &r, win, pixelproc, mask);
  231.               else           scanline(y, &r, &l, win, pixelproc, mask);
  232.             y++;
  233.             increment(&l, &dl, mask);
  234.             increment(&r, &dr, mask);
  235.         }
  236.     }
  237. }
  238.  
  239.  
  240. /* scanline: output scanline by sampling polygon at Y=y+.5 */
  241.  
  242. static scanline(y, l, r, win, pixelproc, mask)
  243. int y, mask;
  244. Poly_vert *l, *r;
  245. Window *win;
  246. void (*pixelproc)();
  247. {
  248.     int x, lx, rx;
  249.     Poly_vert p, dp;
  250.  
  251.     mask &= ~POLY_MASK(sx);        /* stop interpolating screen x */
  252.     lx = ceil(l->sx-.5);
  253.     if (lx<win->x0) lx = win->x0;
  254.     rx = floor(r->sx-.5);
  255.     if (rx>win->x1) rx = win->x1;
  256.     if (lx>rx) return;
  257.     incrementalize_x(l, r, &p, &dp, lx, mask);
  258.     for (x=lx; x<=rx; x++) {        /* scan in x, generating pixels */
  259.         (*pixelproc)(x, y, &p);
  260.         increment(&p, &dp, mask);
  261.     }
  262. }
  263.  
  264. /*
  265.  * incrementalize_y: put intersection of line Y=y+.5 with edge  
  266.  * between points p1 and p2 in p, put change with respect to y in dp  
  267.  */
  268.  
  269. static incrementalize_y(p1, p2, p, dp, y, mask)
  270. register double *p1, *p2, *p, *dp;
  271. register int mask;
  272. int y;
  273. {
  274.     double dy, frac;
  275.  
  276.     dy = ((Poly_vert *)p2)->sy - ((Poly_vert *)p1)->sy;
  277.     if (dy==0.) dy = 1.;
  278.     frac = y+.5 - ((Poly_vert *)p1)->sy;
  279.  
  280.     for (; mask!=0; mask>>=1, p1++, p2++, p++, dp++)
  281.         if (mask&1) {
  282.             *dp = (*p2-*p1)/dy;
  283.             *p = *p1+*dp*frac;
  284.         }
  285. }
  286.  
  287.  
  288. /*
  289.  * incrementalize_x: put intersection of line X=x+.5 with 
  290.  * edge between points p1 and p2 in p,
  291.  *  put change with respect to x in dp
  292.  */
  293.  
  294. static incrementalize_x(p1, p2, p, dp, x, mask)
  295. register double *p1, *p2, *p, *dp;
  296. register int mask;
  297. int x;
  298. {
  299.     double dx, frac;
  300.  
  301.     dx = ((Poly_vert *)p2)->sx - ((Poly_vert *)p1)->sx;
  302.     if (dx==0.) dx = 1.;
  303.     frac = x+.5 - ((Poly_vert *)p1)->sx;
  304.  
  305.     for (; mask!=0; mask>>=1, p1++, p2++, p++, dp++)
  306.         if (mask&1) {
  307.             *dp = (*p2-*p1)/dx;
  308.             *p = *p1+*dp*frac;
  309.         }
  310. }
  311.  
  312. static increment(p, dp, mask)
  313. register double *p, *dp;
  314. register int mask;
  315. {
  316.     for (; mask!=0; mask>>=1, p++, dp++)
  317.         if (mask&1)
  318.             *p += *dp;
  319. }
  320.  
  321.  
  322. /*
  323.  * poly_clip.c: homogeneous 3-D convex polygon clipper
  324.  *
  325.  * Paul Heckbert    1985, Dec 1989
  326.  */
  327.  
  328. #include "poly.h"
  329.  
  330. #define SWAP(a, b, temp)    {temp = a; a = b; b = temp;}
  331. #define COORD(vert, i)  ((double *)(vert))[i]
  332.  
  333. #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  334.     poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
  335.     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  336.     SWAP(p, q, r); \
  337. }
  338.  
  339.  
  340. /*
  341.  * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
  342.  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each              
  343.  * vertex, testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1, 
  344.  * and similar tests for y and z, for each vertex v of the polygon.
  345.  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  346.  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
  347.  * Otherwise, if the polygon is cut by the box, p1 is modified and
  348.  * POLY_CLIP_PARTIAL is returned.
  349.  */
  350.  
  351. int poly_clip_to_box(p1, box)
  352. register Poly *p1;
  353. register Poly_box *box;
  354. {
  355.     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, 
  356.         z1out = 0;
  357.     register int i;
  358.     register Poly_vert *v;
  359.     Poly p2, *p, *q, *r;
  360.  
  361.     /* count vertices "outside" with respect to each */
  362.     /* of the six planes */
  363.     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
  364.         if (v->sx < box->x0*v->sw) x0out++;    /* out on left */
  365.         if (v->sx > box->x1*v->sw) x1out++;    /* out on right */
  366.         if (v->sy < box->y0*v->sw) y0out++;    /* out on top */
  367.         if (v->sy > box->y1*v->sw) y1out++;    /* out on bottom */
  368.         if (v->sz < box->z0*v->sw) z0out++;    /* out on near */
  369.         if (v->sz > box->z1*v->sw) z1out++;    /* out on far */
  370.     }
  371.  
  372.     /* check if all vertices inside */
  373.     if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
  374.  
  375.     /* check if all vertices are "outside" any of the six planes */
  376.     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
  377.         y1out==p1->n || z0out==p1->n || z1out==p1->n) {
  378.         p1->n = 0;
  379.         return POLY_CLIP_OUT;
  380.     }
  381.  
  382.  
  383.     /*
  384.      * now clip against each of the planes that might cut the polygon,
  385.      * at each step toggling between polygons p1 and p2
  386.      */
  387.     p = p1;
  388.     q = &p2;
  389.     if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
  390.     if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
  391.     if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
  392.     if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
  393.     if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
  394.     if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
  395.  
  396.     /* if result ended up in p2 then copy it to p1 */
  397.     if (p==&p2)
  398.         bcopy(&p2, p1, sizeof(Poly)-
  399.             (POLY_NMAX-p2.n)*sizeof(Poly_vert));
  400.     return POLY_CLIP_PARTIAL;
  401. }
  402.  
  403. /*
  404.  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  405.  * copying the portion satisfying sign*s[index] < k*sw into q,
  406.  * where s is a Poly_vert* cast as a double*.
  407.  * index is an index into the array of doubles at each vertex, such that
  408.  * s[index] is sx, sy, or sz (screen space x, y, or z).
  409.  * Thus, to clip against xmin, use
  410.  *    poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  411.  * and to clip against xmax, use
  412.  *    poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  413.  */
  414.  
  415. void poly_clip_to_halfspace(p, q, index, sign, k)
  416. Poly *p, *q;
  417. register int index;
  418. double sign, k;
  419. {
  420.     register int m;
  421.     register double *up, *vp, *wp;
  422.     register Poly_vert *v;
  423.     int i;
  424.     Poly_vert *u;
  425.     double t, tu, tv;
  426.  
  427.     q->n = 0;
  428.     q->mask = p->mask;
  429.  
  430.  
  431.     /* start with u=vert[n-1], v=vert[0] */
  432.     u = &p->vert[p->n-1];
  433.     tu = sign*COORD(u, index) - u->sw*k;
  434.     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  435.     /* on old polygon (p), u is previous vertex, v is current vertex */
  436.     /* tv is negative if vertex v is in */
  437.         tv = sign*COORD(v, index) - v->sw*k;
  438.         if (tu<=0. ^ tv<=0.) {
  439.             /* edge crosses plane; add intersection point to q */
  440.             t = tu/(tu-tv);
  441.             vp = (double *)v;
  442.             wp = (double *)&q->vert[q->n];
  443.             for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
  444.                 if (m&1) *wp = *up+t*(*vp-*up);
  445.             q->n++;
  446.         }
  447.         if (tv<=0.)        /* vertex v is in, copy it to q */
  448.             q->vert[q->n++] = *v;
  449.     }
  450. }
  451.  
  452.  
  453. /*
  454.  * scantest.c: use poly_scan() for Gouraud shading and z-buffer demo.
  455.  * Given the screen space X, Y, and Z of N-gon on command line,
  456.  * print out all pixels during scan conversion.
  457.  * This code could easily be modified to actually read and write pixels.
  458.  *
  459.  * Paul Heckbert    Dec 1989
  460.  */
  461.  
  462. #include <stdio.h>
  463. #include <math.h>
  464. #include "poly.h"
  465.  
  466. #define XMAX 1280    /* hypothetical image width */
  467. #define YMAX 1024    /* hypothetical image height */
  468.  
  469. #define FRANDOM() ((rand()&32767)/32767.)   
  470.         /* random number between 0 and 1 */
  471.  
  472. void pixelproc();
  473.  
  474.  
  475. main(ac, av)
  476. int ac;
  477. char **av;
  478. {
  479.     int i;
  480.     Poly p;
  481.     static Window win = {0, 0, XMAX-1, YMAX-1};
  482.         /* screen clipping window */
  483.  
  484.     if (ac<2 || ac != 2+3*(p.n = atoi(av[1]))) {
  485.         fprintf(stderr, 
  486.             "Usage: scantest N X1 Y1 Z1 X2 Y2 Z2 ... XN YN ZN\n");
  487.         exit(1);
  488.     }
  489.     for (i=0; i<p.n; i++) {
  490.         p.vert[i].sx = atof(av[2+3*i]);    /* set screen space x,y,z */
  491.         p.vert[i].sy = atof(av[3+3*i]);
  492.         p.vert[i].sz = atof(av[4+3*i]);
  493.         p.vert[i].r = FRANDOM();  /* random vertex colors, for kicks */
  494.         p.vert[i].g = FRANDOM();
  495.         p.vert[i].b = FRANDOM();
  496.     }
  497.     /* interpolate sx, sy, sz, r, g, and b in poly_scan */
  498.     p.mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz) |
  499.         POLY_MASK(r) | POLY_MASK(g) | POLY_MASK(b);
  500.  
  501.     poly_print("scan converting the polygon", &p);
  502.     
  503.     poly_scan(&p, &win, pixelproc);    /* scan convert! */
  504. }
  505.  
  506. static void pixelproc(x, y, point)
  507.         /* called at each pixel by poly_scan */
  508. int x, y;
  509. Poly_vert *point;
  510. {
  511.     printf("pixel (%d,%d) screenz=%g rgb=(%g,%g,%g)\n",
  512.         x, y, point->sz, point->r, point->g, point->b);
  513.  
  514.     /*
  515.      * in real graphics program you could read and write pixels, e.g.:
  516.      *
  517.      *    if (point->sz < zbuffer_read(x, y)) {
  518.      *        image_write_rgb(x, y, point->r, point->g, point->b);
  519.      *        zbuffer_write(x, y, point->sz);
  520.      *  }
  521.      */
  522. }
  523.  
  524. /*
  525.  * fancytest.c: subroutine illustrating the use of poly_clip and poly_scan
  526.  * for Phong-shading and texture mapping.
  527.  * Note: lines enclosed in angle brackets "<", ">" should be 
  528.  * replaced with the code described.
  529.  * Makes calls to hypothetical packages "shade", "image", "texture",   
  530.  * "zbuffer".
  531.  * Paul Heckbert    Dec 1989
  532.  */
  533.  
  534. #include <stdio.h>
  535. #include <math.h>
  536. #include "poly.h"
  537.  
  538. #define XMAX 1280    /* hypothetical image width */
  539. #define YMAX 1024    /* hypothetical image height */
  540. #define LIGHT_INTEN 255        /* light source intensity */
  541.  
  542. void pixelproc();
  543.  
  544. fancytest()
  545. {
  546.     int i;
  547.     double WS[4][4];    /* world space to screen space transform */
  548.     Poly p;        /* a polygon */
  549.     Poly_vert *v;
  550.  
  551.     static Poly_box box = {0, XMAX-1, 0, YMAX-1, -32678, 32767};
  552.     /* 3-D screen clipping box */
  553.  
  554.     static Window win = {0, 0, XMAX-1, YMAX-1};
  555.     /* 2-D screen clipping window */
  556.  
  557.     <initialize world space position (x,y,z), normal (nx,ny,nz), and     texture position (u,v) at each vertex of p; set p.n>
  558.     <set WS to world-to-screen transform>
  559.  
  560.     /* transform vertices from world space to homogeneous */
  561.     /*   screen space */
  562.     for (i=0; i<p.n; i++) {
  563.         v = &p.vert[i];
  564.         mx4_transform(v->x, v->y, v->z, 1., 
  565.             WS, &v->sx, &v->sy, &v->sz, &v->sw);
  566.     }
  567.  
  568.  
  569.     /* interpolate sx, sy, sz, sw, nx, ny, nz, u, v in poly_clip */
  570.     p.mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz) |             POLY_MASK(sw) | POLY_MASK(nx) | POLY_MASK(ny) | POLY_MASK(nz) |
  571.         POLY_MASK(u) | POLY_MASK(v);
  572.  
  573.     poly_print("before clipping", &p);
  574.     if (poly_clip_to_box(&p, &box) == POLY_CLIP_OUT)    /* clip polygon */
  575.         return;                        /* quit if off-screen */
  576.  
  577.     /* do homogeneous division of screen position, texture position */
  578.     for (i=0; i<p.n; i++) {
  579.         v = &p.vert[i];
  580.         v->sx /= v->sw;
  581.         v->sy /= v->sw;
  582.         v->sz /= v->sw;
  583.         v->u /= v->sw;
  584.         v->v /= v->sw;
  585.         v->q = 1./v->sw;
  586.     }
  587.     /*
  588.      * previously we ignored q (assumed q=1),
  589.      *  henceforth ignore sw (assume sw=1)
  590.      * Interpolate sx, sy, sz, nx, ny, nz, u, v, q in poly_scan
  591.      */
  592.     p.mask &= ~POLY_MASK(sw);
  593.     p.mask |= POLY_MASK(q);
  594.  
  595.     poly_print("scan converting the polygon", &p);
  596.     poly_scan(&p, &win, pixelproc);    /* scan convert! */
  597. }
  598.  
  599. static void pixelproc(x, y, pt)    
  600.     /* called at each pixel by poly_scan */
  601. int x, y;
  602. Poly_vert *pt;
  603. {
  604.     int sz, u, v, inten;
  605.     double len, nor[3], diff, spec;
  606.  
  607.  
  608.     sz = pt->sz;
  609.     if (sz < zbuffer_read(x, y)) {
  610.         len = sqrt(pt->nx*pt->nx + pt->ny*pt->ny + pt->nz*pt->nz);
  611.         nor[0] = pt->nx/len;        /* unitize the normal vector */
  612.         nor[1] = pt->ny/len;
  613.         nor[2] = pt->nz/len;
  614.         shade(nor, &diff, &spec);    
  615.                         /* compute specular and diffuse coeffs*/
  616.         u = pt->u/pt->q;        /* do homogeneous div. of texture pos */
  617.         v = pt->v/pt->q;
  618.         inten = texture_read(u, v)*diff + LIGHT_INTEN*spec;
  619.         image_write(x, y, inten);
  620.         zbuffer_write(x, y, sz);
  621.     }
  622. }
  623.  
  624. /* mx4_transform: transform 4-vector p by matrix m */
  625. /*  yielding q: q = p*m */
  626.  
  627. mx4_transform(px, py, pz, pw, m, qxp, qyp, qzp, qwp)
  628. double px, py, pz, pw, m[4][4], *qxp, *qyp, *qzp, *qwp;
  629. {
  630.     *qxp = px*m[0][0] + py*m[1][0] + pz*m[2][0] + pw*m[3][0];
  631.     *qyp = px*m[0][1] + py*m[1][1] + pz*m[2][1] + pw*m[3][1];
  632.     *qzp = px*m[0][2] + py*m[1][2] + pz*m[2][2] + pw*m[3][2];
  633.     *qwp = px*m[0][3] + py*m[1][3] + pz*m[2][3] + pw*m[3][3];
  634. }
  635.  
  636.  
  637.  
  638.  
  639.  
  640.